An information flow includes of a sequence of messages generated at a given rate by a common source. Each message within a specific information flow contains one or more fragments. Each information flow may be assigned to a unique queue while waiting to be scheduled for transmission. Multiple queues may be defined to hold different groups of messages in multiple information flows. A computing system may process a set of information flows at a fixed rate, where the queues are processed by priority. Specifically, each queue may be assigned a priority such that messages located within in a high priority queue may be processed by the computing system before messages located within in a lower priority queue. However, it is to be understood that a fragment located within in a lower priority queue that is currently under processing may not be preempted by a fragment located within a higher priority queue. In other words, the computing system finishes processing the current fragment before a subsequent fragment having a higher priority is processed.
The latency of each message may be defined as its total waiting time within the computing system. The total waiting time of a message may be measured from the time the message is added to the system, which is referred to as the message's arrival time, to the time the message is removed from the system, which is referred to as the message's a departure time. The worst case latency of a specific information flow may be defined by the maximum latency of any of the messages located within the information flow, where messages may arrive at any time so long as all timing constraints are satisfied. The backlog of each queue may be defined as a total length of all of the messages waiting within the queue at a specific time. The worst case backlog of a specific queue may be defined by the maximum backlog of the queue at any time, where messages may arrive at any time so long as the messages satisfy all given timing constraints. The worst case latency and backlog may be used to verify and certify performance characteristics of certain safety systems such as, for example, flight control systems in an avionics system.
There are various approaches that may be used to analyze the latency of information flows as well as the backlog of queues processed by a computing system. However, these approaches may each have unique drawbacks that make them unsuitable for determining the worst case latency and backlog. For example, in one approach, a queuing theory such as Little's Law may be used to analyze the latency and backlog. When utilizing a queueing theory, it is assumed that messages arrive at a given probability distribution, and the processing time of the messages follows a given, but usually different, probability distribution. Accordingly, queuing theory may only be used to determine an average latency and backlog, instead of the worst case latency and backlog.
Network calculus is another approach for analyzing the latency of information flows as well as the backlog of queues processed by a computing system. Network calculus may derive pessimistic bounds based on the worst case latencies and backlogs. However, pessimistic bounds are often far from the real values of the worst case latencies and backlogs, and are not guaranteed to be reachable. Moreover, when pessimistic bounds are utilized, resources may be wasted or underutilized in order to ensure the pessimistic bounds of information flow latencies are small enough to meet latency requirements.
In yet another approach, simulation methods may be utilized to analyze the latency of information flows as well as the backlog of queues processed by a computing system. The maximum latency and backlog may be collected from numerous rounds of simulation. However, the maximum latencies and backlogs that are determined using simulation methods are not guaranteed to be the actual worst cases, since the real worst case scenario may never actually be generated during simulation. Indeed, it should be appreciated that simulations do not necessarily generate nor guarantee worst case scenarios. Therefore, latency and backlog parameters based on simulation may not be used as the basis for the verification and certification of system performance characteristics of safety systems.
Mathematical programming, such as mixed integer nonlinear programming, has also been used to analyze the latency of information flows as well as the backlog of queues processed by a computing system. However, it may be challenging to create a high-fidelity model having the correct variables and parameters. Thus, there exists a continuing need in the art for an improved approach to determine the worst case latency of information flows and the worst case backlog of queues in a configuration processed by a computing system.